package sort.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

import sort.record.Record;
import sort.record.Records;

/**
 * @author masaru-gotou
 *
 */
public class BucketSort extends Sorter {
	
	public BucketSort() {
	}
	
	/* 
	 * @see sort.Sorter#sort(sort.Records)
	 */
	@Override
	public Records sort(Records records) {
		// バケツの用意（バケツはキーごとのハッシュテーブル）
		Map<Integer, List<Record>> buckets = new TreeMap<Integer, List<Record>>();
		// レコードをバケツに入れる
		for ( Record rec : records ) {
			List<Record> bucket = buckets.get(rec.getKey());
			if ( bucket == null ) {
				bucket = new ArrayList<Record>();
				buckets.put(rec.getKey(), bucket);
			}
			bucket.add(rec);
		}
		// バケツの順に取り出し
		Records sorted = new Records();
		for (List<Record> b : buckets.values()) {
			for (Record record : b) {
				sorted.add(record);
				setChanged();
				notifyObservers(sorted);
			}
		}
		return sorted;
	}

	@Override
	public String getName() {
		return "Bucket Sort";
	}

}
